home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 090 / cmln0785.arc / CROSSTH.LTG next >
Text File  |  1986-02-27  |  7KB  |  219 lines
  1.                     CrossThoughts - July 1985
  2.  
  3.                            Listinτ 1«
  4.  
  5. PP╠ codσ fo≥ searchinτ iε ß B½ tree
  6.  
  7. ---------------------------------------------------------B½ tree
  8.  
  9. -- DAT┴ TYP┼ DECLARATION¼ Pasca∞ style
  10.  
  11. Leaf_Reπ ╜ RECORD
  12.         Leaf_Left¼ Leaf_Right¼ Count_Leaf_Key║ INTEGER
  13.         Leaf_Ke∙ ║ ARRAY[1..MAX_KEY+1▌ O╞ Key_Data
  14.         Leaf_Pt≥ ║ ARRAY[1..MAX_KEY+1▌ O╞ INTEGER
  15. EN─ RECORD
  16.  
  17. Node_Rec = RECORD
  18.         Count_Node_Key : INTEGER
  19.         Node_Key : ARRAY[1..MAX_KEY+1] OF Key_Data
  20.         Node_Ptr : ARRAY[1..MAX_KEY+1] OF INTEGER
  21. END RECORD
  22.  
  23. -- VARIABLE DECLARATION 
  24.  
  25. Leaf : Leaf_Rec
  26. Node : Node_Rec
  27. ROOT, HEIGHT, MAX_KEY, NUM_PAGE : INTEGER
  28.  
  29.  
  30. PROCEDURE Search(Soughtkey : Key_Data
  31.                  ROOT, HEIGHT : INTEGER
  32.                  VAR Found : BOOLEAN
  33.                  VAR SoughtLeaf, Sought_Loc : INTEGER
  34.                  VAR Leaf : Leaf_Rec)
  35.  
  36. -- Search procedure for B+ tree
  37.  
  38.  
  39. Found = FALSE
  40. IF HEIGHT > 0 THEN
  41.     INITIALIZE: None
  42.     LOOP
  43.     -- loop will conduct gradual descent in B+ tree
  44.     BEGIN IF HEIGHT <= 1 THEN EXIT END IF
  45.         READ "B+TREE_Key_File",ROOT,Node
  46.         SearchNode(SoughtKey,Node,Found,Sought_Loc)
  47.         ROOT = Node.Node_Ptr[Sought_Loc]
  48.         HEIGHT -= 1
  49.     END LOOP
  50.     TERMINATE: SoughtLeaf = ROOT
  51.                READ "B+TREE_Key_File",SoughtLeaf,Leaf
  52.                SearchLeaf(SoughtKey,Leaf,Found,Sought_Loc)
  53. END IF
  54. END Search
  55. è-------------------------------------------------------------------
  56.  
  57. PROCEDURE SearchNode(SoughtKey : Key_Data; 
  58.                      Node : Node_Rec;
  59.                      VAR Found : BOOLEAN;
  60.                      VAR Sought_Loc : INTEGER)
  61.  
  62. BEGIN
  63.  
  64.     IF SoughtKey < Node.Node_Key[1]
  65.     THEN
  66.       Found = FALSE
  67.       Sought_Loc = 1
  68.  
  69.     ELSE
  70.      INTIALIZE: Sought_Loc = Node.Count_Node_Key
  71.      LOOP
  72.      BEGIN IF (SoughtKey >= Node.Node_Key[Sought_Loc]) OR
  73.               (Sought_Loc <= 1) THEN EXIT END IF
  74.            Sought_Loc -= 1
  75.      END LOOP
  76.      TERMINATE: Found = (SoughtKey = Node.Node_Key[Sought_Loc])
  77.     END IF
  78. END SearchNode
  79.  
  80.  
  81.                            Listing 2.
  82.  
  83.  
  84. PPL code for searching in a B++ tree
  85.  
  86. -------------------------------------------------------B++ tree
  87.  
  88. -- DATA TYPE DECLARATION, Pascal style
  89.  
  90. Leaf_Rec = RECORD
  91.         Leaf_Left, Leaf_Right, Count_Leaf_Key, Node_Above : INTEGER
  92.         Leaf_Key : ARRAY[1..MAX_KEY+1] OF Key_Data
  93.         Leaf_Ptr : ARRAY[1..MAX_KEY+1] OF INTEGER
  94. END RECORD
  95.  
  96. Node_Rec = RECORD
  97.         Count_Node_Key, Parent_Node : INTEGER
  98.         Node_Key : ARRAY[1..MAX_KEY+1] OF Key_Data
  99.         Node_Ptr, ZoomPtr : ARRAY[1..MAX_KEY+1] OF INTEGER
  100. END RECORD
  101.  
  102. -- VARIABLE DECLARATION 
  103.  
  104. Leaf : Leaf_Rec
  105. Node : Node_Rec
  106. ROOT, HEIGHT, MAX_KEY, NUM_PAGE : INTEGER
  107.  
  108. -------------------------------------------------------------------
  109. èPROCEDURE Search(Soughtkey : Key_Data
  110.                  ROOT, HEIGHT : INTEGER
  111.                  VAR Found : BOOLEAN
  112.                  VAR SoughtLeaf, Sought_Loc : INTEGER
  113.                  VAR Leaf : Leaf_Rec)
  114.  
  115. Found = FALSE
  116. IF HEIGHT > 0 THEN
  117.     INITIALIZE: None
  118.     LOOP
  119.     BEGIN IF HEIGHT <= 1 THEN EXIT END IF
  120.         READ #2,ROOT,Node
  121.         SearchNode(SoughtKey,Node,Found,Sought_Loc)
  122.         IF Found THEN HEIGHT = 1;  ROOT = Node.Zoom_Ptr[Sought_Loc]
  123.                  ELSE HEIGHT -= 1; ROOT = Node.Node_Ptr[Sought_Loc]
  124.     END LOOP
  125.     TERMINATE:  SoughtLeaf = ROOT
  126.                 READ #2,SoughtLeaf,Leaf
  127.                 IF NOT Found THEN SearchLeaf(SoughtKey,Leaf,Found,Sought_Loc)
  128.                              ELSE Sought_Loc = MAX_KEY + 1
  129. END IF
  130. END Search
  131.  
  132. -- Procedures SearchNode and SearchLeaf are identical to those used
  133. -- with the B+ tree.
  134.  
  135.  
  136.                            Listing 3.
  137.   
  138.  
  139. PPL code for a heuristic statistical system.
  140.  
  141. PROGRAM SMART_SYSTEM
  142.  
  143. -- Program to study the best model to correlate observed 
  144. -- variables X and Y.  The models used are of the following 
  145. -- general type:
  146.  
  147. --    f(Y) = intercept + slope g(X)
  148.  
  149. -- where f(Y) is some function of variable Y.
  150. -- where g(X) is some function of variable X.
  151.  
  152. -- Performance history file contains the following information
  153. --    MAX_MODEL : the maximum number of models compared
  154. --    Remaining_Models : The number of remaining models
  155. --    MAP(): A string containing MAX_MODEL characters to map the status
  156. --           of each model.  If position i has "Y" then the model is 
  157. --           still considered.  Otherwise it is disqualified.
  158. --    Model records composed of the following:
  159. --        Sum_R2 : Sum of the coefficient of determination values 
  160. --        Sum_Sqr_R2 : Sum of the squares of the coefficient of 
  161. --                     determination values
  162. --        Model_Name : A string containing the model name.
  163. è-- N is the number of data sets processed
  164. -- X() and Y() are the arrays for the observations.
  165.  
  166.  
  167. BEGIN
  168.     Read performance history file
  169.     IF Remaining_Models = 1 THEN DISPLAY "One model, program stopped"
  170.                                  Halt program
  171.     END IF
  172.     Read observed data file
  173.     N += 1
  174.     INITIALIZE: None
  175.     LOOP <Model>
  176.     BEGIN  For Model = 1 TO MAX_MODEL
  177.         INITIALIZE: Set statistical summations to zero
  178.                     i = 1
  179.         LOOP <Data>
  180.         BEGIN IF (i > Num_Data) OR (MAP(Model) <> "Y") 
  181.               THEN EXIT <Data> END IF
  182.           CASE i OF
  183.              WHEN 1 => Xreg = X(i); Yreg = Y(i)     -- Linear model
  184.              WHEN 2 => Xreg = Ln(X(i)); Yreg = Y(i) -- Exponential model
  185.              WHEN 3 => Xreg = X(i); Yreg = Ln(Y(i)) -- Logarithmic model
  186.              WHEN 4 => Xreg = Ln(X(i); Yreg = Ln(Y(i)) -- Power model
  187.           END CASE
  188.           Update summations with values of Xreg and Yreg
  189.           i += 1
  190.         END LOOP <Data>
  191.         TERMINATE: None
  192.         Calculate Slope, intercept and coefficient of determination, R2
  193.         Sum_R2 += R2; Sum_Sqr_R2 += R2 * R2
  194.     END LOOP <Model>
  195.  
  196.     IF N > 3 THEN
  197.         Best = index of model with highest average R2 value.
  198.         INITIALIZE: Display "Best model is";Model_Name(Best)
  199.                     Table_T = "Tabulated" Student-t value calculated
  200.                                at (N-2) degrees of freedom and 
  201.                                selected probability level.
  202.         LOOP <Compare>
  203.         BEGIN For  Model = 1 to MAX_MODEL
  204.             IF (Model <> Best) AND (MAP(Model) = "Y") THEN
  205.                 -- Calculate Student-t statistics
  206.                 Term1 = Sqrt(2/N)
  207.                 Term2 = Sqrt((Sum_Sqr_R2(Best) + Sum_Sqr_R2(Model)
  208.                          - Sqr(Sum_R2(Best))/N - Sqr(Sum_R2(Model))/N)
  209.                          / (2 * N - 2))
  210.                 CalcT = (Sum_R2(Best) - Sum_R2(Model))/(N * Term1 * Term2)
  211.                 IF ABS(CalcT) > Table_T THEN MAP(Model) = "N" 
  212.                                              Remaining_Models -= 1
  213.                 END IF
  214.             END IF
  215.         END LOOP <Compare>
  216.         TERMINATE: Display all models still in competition
  217.     END IFèEND SMART_SYSTEM
  218.  
  219.